package com.zdb.datastructures.sort;

import com.zdb.datastructures.utils.MockDataUtils;
import com.zdb.datastructures.utils.TimeUtils;

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
//        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        int[] arr = MockDataUtils.mock80000IntArr();
        TimeUtils.printNowStr();

        shellSort(arr);

        TimeUtils.printNowStr();

    }

    public static void shellSort(int[] arr) {

        int j = 0;
        for(int gap = arr.length / 2; gap >= 1; gap /= 2) {
//            int gap = arr.length / (2 * (j+1)); // 5
//            System.out.println(gap);

            for (int i = 0; i < gap; i++) {
                for(int ii=0; ii<arr.length/gap-1; ii++) {
                    int insertVal = arr[i + ii + (gap - 1) + 1];
                    int insertIdx = i + ii + (gap - 1) + 1;

                    while (insertIdx > 0 + (gap - 1) && insertVal < arr[insertIdx - (gap - 1)
                            - 1]) {
                        arr[insertIdx] = arr[insertIdx - (gap - 1) - 1];
                        insertIdx -= ((gap - 1) + 1);
                    }
                    arr[insertIdx] = insertVal;
                }
            }
//            System.out.println("第" + (++j) + "次排序，=" + Arrays.toString(arr));
        }

    }
}
